//Linkwish's code
#include<bits/stdc++.h>
#define endl '\n'
#define si inline
#define fi first
#define se second
using namespace std;
typedef long long ll;typedef __int128 li;typedef long double ld;
typedef pair<int,int> pii;typedef pair<ll,ll> pll;
typedef const int ci;typedef const ll cl;ci iinf=INT_MAX;cl linf=LLONG_MAX;
template<typename T>si bool gmax(T &x,const T y){if(x<y)return x=y,1;return 0;}
template<typename T>si bool gmin(T &x,const T y){if(y<x)return x=y,1;return 0;}

namespace LinkWish{

	char buf[1<<16],*bp1,*bp2;
	si void init(){if(bp1==bp2)bp2=(bp1=buf)+fread(buf,1,1<<15,stdin);}
	si char Texas(){return (init(),bp1!=bp2)?*bp1++:EOF;}
	template<typename T>
	si void read(T &x){
		char ch=Texas();for(;ch<'0'||ch>'9';ch=Texas());
		for(x=0;ch>='0'&&ch<='9';ch=Texas())x=x*10+(ch-'0');
	}

	ci BUFSZ=1<<16;
	char wrbuf[BUFSZ],*curat=wrbuf;
	si void Flush(){fwrite(wrbuf,1,curat-wrbuf,stdout),curat=wrbuf;}
	si void putch(char ch){
		(*curat++)=ch;
		if(curat-wrbuf==BUFSZ)Flush();
	}
	int stk[60],top;
	si void write(ll x){
		if(x==0)return putch('0'),void();
		for(;x!=0;x/=10)stk[++top]=x%10;
		for(;top!=0;top--)putch('0'+stk[top]);
	}
	
	ci N=400005;

	int n;
	
	mt19937 R(40094229);
	struct Hoshino{
		int ls,rs;
		int key,sz;
		ll sum,v;
		li ss;
	}t[N<<1];

	int rt1,rt2,cnt;
	si int np(ll v){
		cnt++,t[cnt].ls=t[cnt].rs=0;
		t[cnt].key=R(),t[cnt].sz=1;
		t[cnt].sum=t[cnt].v=t[cnt].ss=v;
		return cnt;
	}

	si void push_up(int x){
		t[x].sz=t[t[x].ls].sz+t[t[x].rs].sz+1;
		t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum+t[x].v;
		t[x].ss=t[t[x].ls].ss+t[x].v+t[t[x].rs].ss;
		t[x].ss+=t[t[x].ls].sum*(t[t[x].rs].sz+1);
		t[x].ss+=t[x].v*t[t[x].rs].sz;
	}
	void split(int x,int &l,int &r,int k){
		if(x==0)return l=r=0,void();
		if(t[t[x].ls].sz>=k)r=x,split(t[x].ls,l,t[x].ls,k);
		else l=x,split(t[x].rs,t[x].rs,r,k-t[t[x].ls].sz-1);
		push_up(x);
	}
	void splitv1(int x,int &l,int &r,ll k){
		if(x==0)return l=r=0,void();
		if(t[x].v<=k)l=x,splitv1(t[x].rs,t[x].rs,r,k);
		else r=x,splitv1(t[x].ls,l,t[x].ls,k);
		push_up(x);
	}
	void splitv2(int x,int &l,int &r,ll k){
		if(x==0)return l=r=0,void();
		if(t[x].v>=k)l=x,splitv2(t[x].rs,t[x].rs,r,k);
		else r=x,splitv2(t[x].ls,l,t[x].ls,k);
		push_up(x);
	}
	int merge(int x,int y){
		if(x==0||y==0)return x+y;
		if(t[x].key<t[y].key)return t[x].rs=merge(t[x].rs,y),push_up(x),x;
		return t[y].ls=merge(x,t[y].ls),push_up(y),y;
	}
	bool count(int x,ll k){
		if(t[x].v==k)return true;
		if(x==0)return false;
		if(k<t[x].v)return count(t[x].ls,k);
		return count(t[x].rs,k);
	}

	si ll ask(int x,int k){
		ll res=0;
		while(x!=0&&k!=0){
			if(t[t[x].ls].sz>=k)x=t[x].ls;
			else{
				res+=t[t[x].ls].sum+t[x].v;
				k-=t[t[x].ls].sz+1,x=t[x].rs;
			}
		}
		return res;
	}

	si ll calc(){
		int l=1,r=t[rt1].sz-1,res=t[rt1].sz;
		for(int mid=(l+r)>>1;l<=r;mid=(l+r)>>1){
			if(ask(rt1,mid+1)>=ask(rt2,mid))res=mid,r=mid-1;
			else l=mid+1;
		}

		//for(int i=1;i<=t[rt1].sz;i++)cout<<ask(rt1,i)<<' ';
		//cout<<endl;
		//for(int i=1;i<=t[rt2].sz;i++)cout<<ask(rt2,i)<<' ';
		//cout<<endl;
		//cout<<res<<endl;

		li ans=0;
		int x,y;split(rt2,x,y,res);
		ans=t[x].sum+t[y].sz*t[x].sum+t[y].ss;
		rt2=merge(x,y);
		
		ll vv=0;
		for(int now=rt1;now!=0;now=t[now].ls)vv=t[now].v;
		ans-=vv;

		split(rt1,x,y,res);
		ans-=t[y].sz*t[x].sum+t[y].ss,rt1=merge(x,y);

		return ans;
	}

	//si ll calc(){
	//	if(t[rt1].sz<=1)return 0;
	//	int res=0;
	//	int l1,l2=0,r1=0,r2=0;
	//	split(rt1,l1,rt1,1);
	//	for(int i=__lg(t[rt1].sz);~i;i--){
	//		if(t[rt1].sz>=(1<<i)){
	//			int x,y,xx,yy;
	//			split(rt1,x,y,(1<<i));
	//			split(rt2,xx,yy,(1<<i));
	//			if(t[l1].sum+t[x].sum>=t[l2].sum+t[xx].sum)
	//				rt1=x,rt2=xx,r1=merge(y,r1),r2=merge(yy,r2);
	//			else rt1=y,rt2=yy,l1=merge(l1,x),l2=merge(l2,xx),res+=(1<<i);
	//		}
	//	}
	//	res++;

	//	rt1=merge(merge(l1,rt1),r1);
	//	rt2=merge(merge(l2,rt2),r2);

	//	li ans=0;
	//	int x,y;split(rt2,x,y,res);
	//	ans=t[x].sum+t[y].sz*t[x].sum+t[y].ss;
	//	rt2=merge(x,y);

		
	//	ll vv=0;
	//	for(int now=rt1;now!=0;now=t[now].ls)vv=t[now].v;
	//	ans-=vv;

	//	split(rt1,x,y,res);
	//	ans-=t[y].sz*t[x].sum+t[y].ss,rt1=merge(x,y);

	//	return ans;
	//}

	si void change(ll k){
		if(count(rt1,k)){
			int x,y,z;
			splitv1(rt1,x,y,k-1);
			splitv1(y,y,z,k);
			rt1=merge(x,z);

			splitv2(rt2,x,y,k+1);
			splitv2(y,y,z,k);
			rt2=merge(x,z);
		}
		else{
			int x,y;
			splitv1(rt1,x,y,k);
			rt1=merge(merge(x,np(k)),y);

			splitv2(rt2,x,y,k);
			rt2=merge(merge(x,np(k)),y);
		}
	}

	void mian(){
		read(n);
		while(n--){
			ll x;read(x);
			change(x);
			write(calc());
			putch('\n');
		}
		Flush();
	}
}

signed main(){
	freopen("kte.in","r",stdin);
	freopen("kte.out","w",stdout);
	LinkWish::mian();
	return 0;
}